//
// Created by Administrator on 2021/11/15.
//

/*拓扑排序的实现:
 * ①从AOV网中选择一个没有前驱（入度为0)的顶点并输出
 * ②从网中删除该顶点和所有以它为起点的有向边。
 * ③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止
*/
#include <cstdio>
#include <commctrl.h>

#define MaxVertexNum 100
typedef int InfoType;
typedef char VertexType;
//图中顶点数目的最大值
typedef struct ArcNode {
    //边表结点
    int adjvex; //该弧所指向的顶点的位置
    struct ArcNode *nextarc;//指向下一条弧的指针
    InfoType info; //网的边权值
} ArcNode;
typedef struct VNode {
    //顶点表结点
    VertexType data;//顶点信息
    ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
} VNode, AdjList[MaxVertexNum];
typedef struct {
    AdjList vertices;//邻接表
    int vexnum;//图的顶点数
    int arcnum;//图的弧数
} Graph;//Graph是以邻接表存储的图类型

typedef struct {
} *StackNode;

void InitStack(StackNode s);

void Push(StackNode s, int i);

bool IsEmpty(StackNode s);

void Pop(StackNode s, int &i);

bool Topologicalsort(Graph G) {
    StackNode S;
    InitStack(S);//初始化栈，存储入度为0的顶点
    int indegree[G.vexnum];
    int print[G.vexnum];
    for (int i = 0; i < G.vexnum; i++) {
        if (indegree[i] == 0) {
            Push(S, i);//将所有入度为0的顶点进栈
        }
    }
    int count = 0;//计数，记录当前已经输出的顶点数
    while (!IsEmpty(S)) {
        //栈不空， 则存在入度为0的顶点
        int i = 0;
        Pop(S, i);//栈顶元素出栈
        print[count++] = i;//输出顶点i
        for (ArcNode *p = G.vertices[i].firstarc; p; p = p->nextarc) {
            //将所有i指向的顶点的入度减1，并且将入度减为0的顶点压
            int v = p->adjvex;
            if (!(--indegree[v])) {
                Push(S, v);//入度为0，则入栈
            }
        }
    }//while
    return (count >= G.vexnum);//拓扑排序成功,无回路
}

/************************************************************/
/*逆拓扑排序的实现(DFS算法)*/
bool visited[MaxVertexNum];

VertexType FirstNeighbor(Graph g, int i);

VertexType NextNeighor(Graph g, int i, VertexType w);

void print(int i);

void DFS(Graph G, int v) {
    //从顶点v出发，深度优先遍历图G
    visited[v] = true;//设已访问标记
    for (VertexType w = FirstNeighbor(G, v); w >= 0; w = NextNeighor(G, v, w))
        if (!visited[w]) {
            //w为u的尚未访问的邻接顶点
            DFS(G, w);
        } //if
    print(v);//输出顶点
}

void DFSTraverse(Graph G) {
    //对图G进行深度优先遍历
    for (int v = 0; v < G.vexnum; ++v)
        visited[v] = false;//初始化已访问标记数据
    for (int v = 0; v < G.vexnum; ++v)//本代码中是从v=0开始遍历
        if (!visited[v])
            DFS(G, v);
}
/*以上并不适用有环图，应加以修改*/
